home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / SOUNDEX.C < prev    next >
C/C++ Source or Header  |  1989-04-04  |  4KB  |  125 lines
  1.  
  2. Following is an implementation of the Soundex keying routine.  It uses
  3. the first letter and a function of the next few letters of a name to
  4. derive a four-character key.  The algorithm tends to cluster names
  5. which sound similar.  It was originally developed by the Bureau of the
  6. Census to let them find an individual's record even if the name is
  7. slightly misspelled.
  8.  
  9. There was another version on the net, but when I looked at it, the 
  10. implementation seemed excessively arcane.  This routine is reasonably
  11. straightforward, documented, and includes test data for verification.
  12.  
  13. Released to the public domain.  Have fun.
  14.  
  15. -Dean
  16.  
  17. ---- cut (and check for .signature at the end) --- cut --- cut --- cut ---
  18. /* Note: code text edited with a 4-character tab stop.
  19.  *
  20.  * This implementation of the Soundex algorithm is released to the public
  21.  * domain: anyone may use it for any purpose.  See if I care.
  22.  *
  23.  * N. Dean Pentcheff
  24.  * 1/13/89
  25.  * Dept. of Zoology
  26.  * University of California
  27.  * Berkeley, CA  94720
  28.  * dean@violet.berkeley.edu
  29.  *
  30.  * char * soundex( char * )
  31.  *
  32.  * Given as argument: Pointer to a character string.
  33.  * Returns: Pointer to a static string, 4 characters long, plus a terminal
  34.  *    '\0'.  This string is the Soundex key for the argument string.
  35.  * Side effects and limitations:
  36.  *    Does not clobber the string passed in as the argument.
  37.  *    No limit on argument string length.
  38.  *    Assumes a character set with continuously ascending and contiguous
  39.  *       letters within each case and within the digits (e.g. this works for
  40.  *       ASCII and bombs in EBCDIC.  But then, most things do.).
  41.  * Reference: Adapted from Knuth, D.E. (1973) The art of computer programming;
  42.  *    Volume 3: Sorting and searching.  Addison-Wesley Publishing Company:
  43.  *    Reading, Mass. Page 392.
  44.  * Special cases:
  45.  *    Leading or embedded spaces, numerals, or punctuation are squeezed out
  46.  *       before encoding begins.
  47.  *    Null strings or those with no encodable letters return the code 'Z000'.
  48.  * Test data from Knuth (1973):
  49.  *    Euler   Gauss   Hilbert Knuth   Lloyd   Lukasiewicz
  50.  *    E460    G200    H416    K530    L300    L222
  51.  */
  52.  
  53. #include    <string.h>
  54. #include    <ctype.h>
  55.  
  56. char *
  57. soundex(in)
  58.     char    *in;
  59. {
  60.     static    int code[] =
  61.         {  0,1,2,3,0,1,2,0,0,2,2,4,5,5,0,1,2,6,2,3,0,1,0,2,0,2 };
  62.         /* a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z */
  63.     static    char key[5];
  64.     register    char ch;
  65.     register    int last;
  66.     register    int count;
  67.  
  68.     /* Set up default key, complete with trailing '0's */
  69.     key[0] = 'Z';
  70.     key[1] = key[2] = key[3] = '0';
  71.     key[4] = '\0';
  72.  
  73.     /* Advance to the first letter.  If none present, return default key */
  74.     while (*in != '\0'  &&  !isalpha(*in))
  75.         ++in;
  76.     if (*in == '\0')
  77.         return(key);
  78.  
  79.     /* Pull out the first letter, uppercase it, and set up for main loop */
  80.     key[0] = islower(*in) ? toupper(*in) : *in;
  81.     last = code[key[0] - 'A'];
  82.     ++in;
  83.  
  84.     /* Scan rest of string, stop at end of string or when the key is full */
  85.     for (count = 1;  count < 4  &&  *in != '\0';  ++in) {
  86.         /* If non-alpha, ignore the character altogether */
  87.         if (isalpha(*in)) {
  88.             ch = isupper(*in) ? tolower(*in) : *in;
  89.             /* Fold together adjacent letters sharing the same code */
  90.             if (last != code[ch - 'a']) {
  91.                 last = code[ch - 'a'];
  92.                 /* Ignore code==0 letters except as separators */
  93.                 if (last != 0)
  94.                     key[count++] = '0' + last;
  95.             }
  96.         }
  97.     }
  98.  
  99.     return(key);
  100. }
  101.  
  102. #ifdef    TESTPROG
  103. /*
  104.  * If compiled with -DTESTPROG, main() will print back the key for each
  105.  * line from stdin.
  106.  */
  107. #include    <stdio.h>
  108. void
  109. main()
  110. {
  111.     char    instring[80];
  112.  
  113.     while (fgets(instring, 79, stdin) != (char *)NULL)
  114.         printf("%s\n", soundex(instring));
  115. }
  116. #endif    TESTPROG
  117.  
  118. Dean Pentcheff        dean@violet.berkeley.edu
  119. ----------------------------------------------
  120. As an adolescent I aspired to lasting fame, I craved factual certainty, and I
  121. thirsted for a meaningful vision of human life - so I became a scientist.  This
  122. is like becoming an archbishop so you can meet girls.               M. Cartmill
  123.  
  124.  
  125.